ABSTRACCIÓN DE DATOS

“La revolución de la abstracción de datos ha afectado al espectro total del diseño de lenguajes, metodología de la programación y la forma de pensar los programas” (Judy Bishop)

---

Tipos Abstractos de Datos
Tipos de datos primitivos y derivados

En primer lugar, hay que distinguir entre tipos de datos primitivos y derivados:

• Los tipos de datos primitivos son los que están ligados estrechamente a la arquitectura de la máquina: enteros, booleanos, cadenas de caracteres (strings), punto flotante, etc. Cada tipo de datos tiene un conjunto de valores permitidos y una serie de operaciones asociadas. Por ejemplo, el tipo “entero” son números enteros (…, −2, −1, 0, 1, 2, …) y las operaciones son: suma, resta, producto, etc. El tipo “booleano” tiene como valores V (verdadero) y F (falso) y un conjunto de operaciones lógicas (conjunción, disyunción, negación, etc.).
  
  
• Los tipos de datos derivados pueden ser de dos clases:
  
  
  1. Subtipos de datos. Son tipos de datos primitivos restringidos por alguna propiedad (valores posibles, longitud, etc.). Por ejemplo, los números pares, los enteros comprendidos entre 0 y 128, las cadenas de caracteres que solo contienen ceros y unos, las cadenas de caracteres de longitud mayor que 3, los números de 3 dígitos, etc.
     
     
  2. Los supertipos de datos. Son estructuras de tipos o subtipos de datos. Las estructuras pueden ser homogéneas o heterogéneas (o polimórficas). Un ejemplo de estructura homogénea es una secuencia de números enteros. Un ejemplo de estructura heterogénea es una secuencia de elementos compuestos por un entero, un booleano y una cadena de caracteres.

Tipos abstractos de datos

Un tipo abstracto de datos (TAD) está formado por dos capas o niveles:

1. El nivel interior. Es el nivel implementador, que está oculto al usuario. En este nivel se encuentra la estructura de datos. La característica de ocultar los detalles implementadores de un objeto de datos se denomina “encapsulamiento”.
   
   
2. El nivel exterior. Es el nivel conceptual y de utilización, que es la interfaz pública. El interfaz está constituida por un conjunto de operaciones definidas sobre la estructura de datos del nivel interno.

La interfaz pública o externa corresponde al “qué”, a la especificación. La parte privada o interna corresponde al “cómo”, a la implementación.

El TAD tiene la implementación oculta al usuario. Pero si es expuesta, se habla de un tipo de datos “transparente”.

Las operaciones típicas sobre una estructura de datos son: almacenar, recuperar (o acceder), seleccionar, modificar, eliminar, etc. elementos (u objetos) en la estructura de datos. El conjunto de operaciones que pueden realizarse con un TAD es cerrado, es decir, solo se puede acceder a través de la interfaz, que es fija. Por su propia naturaleza, los TADs son estructuras de datos dinámicas.

Un TAD se puede definir como una clase de objetos (o elementos) definidos por una estructura, un conjunto de valores, un conjunto de operaciones y un conjunto de restricciones definidas como precondiciones y postcondiciones.

En POO (Programación Orientada a Objetos), un TAD es una clase de objetos porque la interfaz pública está parametrizada. Una instancia de una clase es un objeto.

Todos los lenguajes de alto nivel tienen TADs predefinidos, pero el usuario puede definir sus propios TADs.


Ejemplos

Estructuras de datos que pueden implementarse como TADs son: conjuntos, secuencias, pilas, colas, vectores, grafos, contenedores, diccionarios, mapas, estructuras algebraicas (grupos, anillos, retículos, etc.), etc. Por ejemplo:

• Una secuencia se puede implementar como una secuencia física (en posiciones contiguas de memoria), como una matriz unidimensional, como una lista enlazada, como una lista doblemente enlazada, etc. En una lista enlazada, los datos se almacenan en nodos. Cada nodo tiene un contenido (los datos) y una dirección que apunta al siguiente elemento de la lista. En una lista doblemente enlazada, cada nodo tiene un contenido y dos direcciones: una que apunta al siguiente elemento y otra que apunta al anterior.
  
  
• Un conjunto se puede implementar como un árbol de dos niveles en el que el nodo superior representa el conjunto y los nodos inferiores sus elementos.
  
  
• Una pila se puede definir por tres operaciones: push (insertar), pop (extraer, eliminando) y peek (acceder sin eliminar al elemento top de la pila). El protocolo es LIFO (last in, first out). En las colas el protocolo es FIFO (first in, first out).

Ventajas de los TADs

Hay dos ventajas principales:

1. Simplifica la programación, pues permite al programador operar con los datos desde un nivel de abstracción superior, de forma conceptual, sin que tenga necesidad de conocer los detalles de su implementación.
   
   
2. La implementación puede variar con el tiempo (por ejemplo, para mejorar el rendimiento o consumir menos recursos), pero no así el interfaz, por lo que el código fuente queda inalterable.

MENTAL y la Abstracción de Datos
La historia de los lenguajes de programación está ligada a una creciente abstracción. Un proceso de abstracción consiste en centrarse en las características esenciales de algo, prescindiendo de lo particular, accesorio o contingente. El problema fundamental en el diseño de sistemas software es reducir la complejidad, y este objetivo pasa necesariamente por el proceso de abstracción. La primera abstracción que apareció fue la procedimental. Posteriormente fueron apareciendo otras abstracciones: objetos, funciones, reglas, eventos, aspectos, agentes, etc., incluyendo los TADs.

• MENTAL, abstracción suprema.
  Es la culminación del proceso de abstracción de los lenguajes de programación. Reduce la complejidad al máximo al tratar con conceptos de supremo nivel de abstracción. Las primitivas semánticas universales son las abstracciones supremas.
  
  La eficiencia en el desarrollo de programas es máxima al trabajar con arquetipos primarios. Nunca fue fácil el programar. Los desarrollos son sencillos, conceptuales, directos, sin preocuparse por su implementación.
  
  
• MENTAL, un lenguaje fundamentado en la abstracción de datos.
  En efecto, las construcciones del lenguaje solo hacen referencia a la semántica y no a sus posibles implementaciones. Por ejemplo, el conjunto {a b c d} o la secuencia (a b c d) son instancias concretas de conjunto y secuencia, respectivamente, pero sin hacer referencia a la forma en que se implementarán, existiendo muchas posibles formas de hacerlo.
  
  
• MENTAL, un lenguaje polimórfico universal.
  Los componentes de las primitivas pueden ser expresiones cualesquiera. Por ejemplo, un conjunto podría ser
  
  {x 7*y "abc" ⟨x+y⟩ ⟨( f(x y) = (x+y x*y) )⟩}
  
  
• MENTAL, la verdadera revolución.
  Judu Bishop [1989] afirma que la abstracción de datos ha sido una verdadera revolución en programación. Pero la verdadera revolución es la de MENTAL, porque supone la abstracción suprema.

La variable como el TAD más simple

Una variable x se puede considerar un TAD dinámico que tiene dos operaciones:

1. Almacenar un valor v en la variable x: (x = v).
   
   
2. Acceder al valor de la variable. Se hace simplemente haciendo mención a x:

x // ev. v

El siguiente nivel en la complejidad de TAD es una variable parametrizada:

( x(y) = z ) // almacenar
x(y) // acceder

en donde x, y, z pueden ser expresiones cualesquiera. Por ejemplo:

( x(a b c) = ⟨( f(u v) = (u+v u*v )⟩ )

( x(a b c) // ev. ⟨( f(u v) = (u+v u*v )⟩ )

Ejemplo de contenedor

Un contenedor está formado por un conjunto de elementos. Cada elemento tiene una clave y unos datos asociados. La clave y los datos pueden ser tan complejos como se desee. Por ejemplo, una clave podría ser una variable parametrizada. Estamos como en el caso anterior.

( clave = datos ) // almacenar

clave // recuperar: se evalúa como datos

( contenedor(clave) = datos ) // almacenar

contenedor(clave) // recuperar: se evalúa como datos

Ejemplos:

(1715 = "abcde")

1715 // ev. "abcde"

( AñoNacimiento(Pepe) = 1936 )

AñoNacimiento(Pepe) // ev. 1936

( LugarNacimiento(Pepe) = "Cartagena" )

LugarNacimiento(Pepe) // ev. "Cartagena" )

En este ejemplo, AñoNacimiento y LugarNacimiento se pueden considerar contenedores.


Ejemplo de pila

Si llamamos s al nombre de la pila y x el valor a añadir, tenemos las siguientes operaciones:

⟨( n(s) := 0 )⟩ // cero elementos (pila vacía)

⟨( push(s x) = ( (n(s) = n(s) + 1) (s(n(s)) = x) ) )⟩

⟨( pop(s) = ( (n(s)>0 →
((s(n(s)) = θ) (n(s) = n(s) − 1) ) )⟩

⟨( top(s) = s(n(s)) )⟩

La pila se ha implementado como una matriz unidimensional, pero podría haberse implementado como una secuencia o de cualquier otra forma, pero desde el punto de vista del usuario, la interfaz no varía.

---

Adenda
Historia de los TADs

• En 1972, David Parnas publicó su seminal trabajo sobre modularización [Parnas, 1972] en el que cada módulo almacenaba datos internos, con un interfaz procedural.
  
  
• En 1974, John Guttag propone por primera vez el concepto de abstracción de datos.
  
  
• Ese mismo año, Barbara Liskov y Stephen Zilles proponen implementar los TADs en el lenguaje CLU [Liskov & Zilles, 1974]. Este artículo tuvo una gran influencia y propició unos años de intensa investigación sobre TADs, que se reflejaron en lenguajes, técnicas y metodologías.
  
  
• En los años 1970s, el lenguaje Turbo Pascal incorporó las Units (Unidades), que eran TADs con encapsulación de datos y modularidad. Este lenguaje fue determinante para la aceptación general de los TADs. Posteriormente se diseñó el lenguaje Ada, que incorporaba los packages (paquetes), que eran TADs.
  
  
• En 1973, Stephen Zilles publica el artículo “Procedural Abstraction: a linguistic protection technique” [Zilles, 1973], en el que mostraba cómo los procedimientos podían ser utilizados para representar objetos de datos. Su noción de abstracción procedural era muy similae a la de los módulos de Parnas. Pero Zilles los veía como datos que incluso podían pasarse como argumentos a otros procedimientos.
  
  
• En 1976, se celebró una conferencia de ACM SIGPLAN sobre Data: Abstraction, Definition and Structure.
  
  
• En 1977 se acuñó el término “abstracción de datos” en el que el foco de atención pasó de los algoritmos (o abstracciones funcionales) a las abstracciones de datos: los procedimientos como vía indirecta para acceder a los datos. Posteriormente aparecieron los términos “tipos de datos encapsulados” y “tipos de datos abstractos”.
  
  
• Hacia 1979, los TADs fueron ampliamente aceptados en los lenguajes de programación.

Bibliografía

• Bishop, Judy. Abstracción de Datos. Paraninfo, 1989.
  
  
• Cardelli, L.; Wegner, P. On understanding types, data abstraction, and polymorphism. Computing Surveys, 17 (4): 471–522, 1986.
  
  
• Cook, William R. Object-Oriented Programming Versus Abstract Data Types. Proceedings of the REX Workshop/School on the Foundations of Object-Oriented Languages, LNCS, Springer –Verlag, pp. 151-178, 1990. Disponible online.
  
  
• Gries, D.; Gehani, N. Some ideas on data types in high-level languages. Coms. of the ACM 20 (6): 414-320, 1977.
  
  
• Guttag, John. Abstract data types and the development of data structures. Coms. of the ACM, 20 (6): 396-404, 1977.
  
  
• Ledgard, H.F.; Taylor, R.W. Two views of data abstraction. Coms. of the ACM 20 (6): 382-384, 1977.
  
  
• Liskov, B.; Ziller, S. Programming with Abstract Data Types. SIGPlan Notices, 9 (4): 50-59, 1974.
  
  
• Liskov, B.; Snyder, A.; Atkinson, R.; Schaffert, C. Abstraction Mechanisms in CLU. Communications of the ACM, 20: 564-576, 1977.
  
  
• Mitchell, J.C.; Plotkin, G.D. Abstract types have existential type. In Proc. of the ACM Symp. on Principles of Programming Languages, 1985.
  
  
• Parnas, David. On the criteria to be used in decomposing systems into modules. Communications of the ACM, 15: 1053–1058, 1972.
  
  
• Parnas, David. A technique for software module specification. Communications of the ACM, 15: 330–336, 1972.
  
  
• Zilles, S.N. Procedural Abstraction: a linguistic protection technique. ACM Sigplan Notices 8 (9): 142-146, 1973.